﻿using System;

namespace _02Recursion_02Game
{
    class Program
    {
        private static int MinStep = int.MaxValue;

        /// <summary>
        /// Width
        /// </summary>
        private static int W = 5;

        /// <summary>
        /// Height
        /// </summary>
        private static int H = 4;

        private static int[,] To = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        private static char[,] Board =
        {
            {' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', 'X', 'X', 'X', 'X', 'X', ' '},
            {' ', 'X', ' ', ' ', ' ', 'X', ' '},
            {' ', 'X', 'X', 'X', ' ', 'X', ' '},
            {' ', ' ', 'X', 'X', 'X', ' ', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' '}
        };

        private static bool[,] Mark = new bool[6, 7];

        static void Main(string[] args)
        {
            Search(3, 2, 3, 5, 0, -1);

            if (MinStep != int.MaxValue)
            {
                Console.WriteLine(MinStep);
            }
            else
            {
                Console.WriteLine("Impossible.");
            }

            Console.ReadKey();
        }

        /// <summary>
        /// 路径搜索函数。
        /// </summary>
        /// <param name="nowX">当前位置 X</param>
        /// <param name="nowY">当前位置 Y</param>
        /// <param name="endX">结束位置 X</param>
        /// <param name="endY">结束位置 Y</param>
        /// <param name="step">已经走过的路径数目</param>
        /// <param name="f">从上一步走到当前位置时的方向</param>
        static void Search(int nowX, int nowY, int endX, int endY, int step, int f)
        {
            // 当前路径数大于 MinStep，返回 -> 优化策略
            if (step > MinStep)
            {
                return;
            }

            if ((nowX == endX) && (nowY == endY))
            {
                MinStep = step < MinStep ? step : MinStep;
                return;
            }

            // 枚举下一步的方向
            for (var i = 0; i < 4; i++)
            {
                var x = nowX + To[i, 0];
                var y = nowY + To[i, 1];

                if ((x > -1) && (x < H + 2) && (y > -1) && (y < W + 2) && ((Board[x, y] == ' ') && (Mark[x, y] == false) ||
                    ((x == endX) && (y == endY) && (Board[x, y] == 'X'))))
                {
                    Mark[x, y] = true;

                    if (f != i)
                    {
                        step++;
                        f = i;
                    }

                    Search(x, y, endX, endY, step, f);

                    // 回溯，该位置未曾走过
                    Mark[x, y] = false;
                }
            }
        }
    }
}
